/* 
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。
一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。


输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]

思路：
当只有一个盘子时，就是从A移动到C，—— 共1次
当有两个盘子时，先把小盘子从A移动到B，再把大盘子移动到C，最后从B移动到C  —— 共3次
当有三个盘子时，小盘子移动到C，中盘子移动到B，小盘子再移动到B，大盘子移动到C，小盘子移动到A，中盘子移动到C，小盘子移动到C  —— 共7次

数学规律： 2的n次方-1

但此题考的是分治，所以试着用递归解题

递归思路：
n-1个盘子从A移动到B，第n个从A移动到C，最后n-1个盘子从B移到C   —— 即每次考虑的是前多少个盘子怎么从A移到C
*/

/**
 * @param {number[]} A
 * @param {number[]} B
 * @param {number[]} C
 * @return {void} Do not return anything, modify C in-place instead.
 */
var hanota = function (A, B, C) {
    let n = A.length,count=0
    let move = function (m, a, b, c) {
        count++
        if (m === 1) {          // 当只有一个时直接加到c中
            c.push(a.pop())
        } else {
            move(m - 1, a, c, b)  // 将 a 上的 n - 1 个 从 a 移到 b
            c.push(a.pop())       // 把 a 中剩下的一个直接放到 c
            move(m - 1, b, a, c)  // 在把 b 上的 n - 1 个 从 b 放到 c
        }
    }
    move(n, A, B, C)
    return count
};


let A = [2, 1, 0], B = [], C = []
let count=hanota(A, B, C)
console.log(C);
console.log(count);